package com.linzm.leetcode.primary.exercises3_20230122;

/**
 * @Author zimingl
 * @Date 2023/1/26 19:09
 * @Description: 黑白方格画
 */
public class Demo36_22 {
    /**
     * 小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。
     * 画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），
     * 所选行数、列数均可为 0。
     * 小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。
     * 注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。
     * 输入：n = 2, k = 2
     * 输出：4
     * 解释：一共有四种不同的方案： 第一种方案：涂第一列； 第二种方案：涂第二列； 第三种方案：涂第一行； 第四种方案：涂第二行。
     *
     * @param args
     */
    public static void main(String[] args) {
        Demo36_22 demo36_22 = new Demo36_22();
        int n = 3, k = 8;
        int paintingPlan = demo36_22.paintingPlan2(n, k);
        System.out.println(paintingPlan);
    }

    /**
     * 按照先行后列的顺序进行填涂，需要注意的地方就是可能会出现一个重复计数的地方，
     * 单独提出来就好了 重复情况为：行涂满，列不涂，列涂满，行不涂
     * @param n n
     * @param k k
     * @return num
     */
    private int paintingPlan2(int n, int k) {
        int hor = 0, ver = 0;//表示水平和垂直情况下填的数目
        int cnt = 0;
        int[] csix = new int[7];
        csix[0] = 1;
        for (int i = 1; i < 7; i++) {
            csix[i] = csix[i - 1] * (n - i + 1) / i;
        }
        if (k == n * n) return 1;
        for (hor = 0; hor * n <= k; hor++) {
            int lef = k - hor * n;
            if (lef % (n - hor) == 0) {
                ver = lef / (n - hor);
                cnt += csix[hor] * csix[ver];
            }

        }
        return cnt;
    }

    // 2 2 4
    // 2 1 0 2 3 0
    // 2 4 1
    private int paintingPlan(int n, int k) {
        if (n == k * k) {
            return 1;
        }
        if (k == 0 || k % n != 0) {
            return 0;
        }
        if (k % n == 0) {
            return combination(n, k) * 2;
        }
        return -1;
    }

    private int combination(int n, int k) {
        k = k / n;
        return (n >= k) ? factorial(n) / factorial(n - k) / factorial(k) : 0;
    }

    private static int factorial(int n) {
        return (n > 1) ? n * factorial(n - 1) : 1;
    }
}
